package com.company.demo9;

import java.util.*;

public class TestHuffmanCode {

    public static void main(String[] args) {
//        String msg = "can you can a can as a can canner can a an.";
//        byte[] bytes = msg.getBytes();
//        //进行赫夫曼编码压缩
//        byte[] b = huffmanZip(bytes);
//        //使用赫夫曼编码进行解码
//        byte[] newBytes = decode(huffCodes,b);
        byte b = 1;
        String s = byteToBitStr(b);
        System.out.println(s);
    }

    /**
     * 使用指定的赫夫曼编码表进行解码
     * @param huffCodes2
     * @param
     * @return
     */
    private static byte[] decode(Map<Byte, String> huffCodes2, byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        //把Byte数组转为一个二进制的字符串
        for (byte b:bytes){
            sb.append(byteToBitStr(b));
        }

        System.out.println(sb.toString());
        //把字符串按照指定的赫夫曼编码进行解码

        return null;
    }

    private static String byteToBitStr(byte b){
        int temp=b;
        temp|=256;
        String str = Integer.toBinaryString(temp);
        return str.substring(str.length()-8);
    }

    /**
     * 进行赫夫曼编码压缩的方法
     * @param bytes
     * @return
     */
    private static byte[] huffmanZip(byte[] bytes) {
        //先统计每一个byte出现的次数，并放入一个集合中
        List<Node> nodes = getNodes(bytes);
        //创建一颗赫夫曼树
        Node tree = createHuffmanTree(nodes);
        //创建一个赫夫曼编码表
        Map<Byte,String> huffCodes = getCodes(tree);
        System.out.println(huffCodes);
        //编码
        byte[] b = zip(bytes,huffCodes);

        return b;
    }

    /**
     * 进行赫夫曼编码
     * @param bytes
     * @param huffCodes
     * @return
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
        StringBuilder sb = new StringBuilder();
        //把需要压缩的byte数组处理成一个二进制的字符串
        for (byte b:bytes){
            sb.append(huffCodes.get(b));
        }
        //定义长度
        int len;
        if (sb.length()%8==0){
            len = sb.length()/8;
        }else {
            len=sb.length()/8+1;
        }
        //用于存储压缩后的byte
        byte[] by = new byte[len];
        //记录新byte的位置
        int index = 0;
        for (int i=0;i<sb.length();i+=8){
            String strByte;
            if (i+8>sb.length()){
                strByte = sb.substring(i);
            }else {
                strByte = sb.substring(i, i + 8);
            }
            byte byt = (byte) Integer.parseInt(strByte,2);
            by[index] = byt;
            index++;
        }

        return by;
    }

    //用于临时存储路径
    static StringBuilder sb = new StringBuilder();
    //用于存储赫夫曼编码
    static Map<Byte, String> huffCodes = new HashMap<>();

    /**
     * 根据赫夫曼树获取赫夫曼编码
     * @param tree
     * @return
     */
    private static Map<Byte, String> getCodes(Node tree) {
        if (tree==null){
            return null;
        }
        getCodes(tree.left,"0",sb);
        getCodes(tree.right,"1",sb);

        return huffCodes;
    }

    private static void getCodes(Node node, String s, StringBuilder sb) {
        StringBuilder sb2 = new StringBuilder(sb);
        sb2.append(s);
        if (node.data==null){
            getCodes(node.left,"0",sb2);
            getCodes(node.right,"1",sb2);
        }else {
            huffCodes.put(node.data,sb2.toString());
        }
    }

    /**
     * 创建赫夫曼树
     * @param nodes
     * @return
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while(nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //取出两个权值最低的二叉树
            Node left = nodes.get(nodes.size()-1);
            Node right = nodes.get(nodes.size()-2);
            //创建一颗新的二叉树
            Node parent = new Node(null, left.weight+right.weight);
            //把之前取出来的两颗二叉树设置为新创建的二叉树的子树
            parent.left=left;
            parent.right=right;
            //把前面取出来的两颗二叉树删掉
            nodes.remove(left);
            nodes.remove(right);
            //把新创建的二叉树放入集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    /**
     * 把byte数组转为node集合
     * @param bytes
     * @return
     */
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        //每一个Byte出现了多少次
        Map<Byte, Integer> counts = new HashMap<>();
        //统计每一个byte出现的次数
        for (byte b:bytes){
            Integer count = counts.get(b);
            if (count==null){
                counts.put(b, 1);
            }else {
                counts.put(b, count+1);
            }
        }
        //把每一个键值对转为一个node对象
        for (Map.Entry<Byte, Integer> entry:counts.entrySet()){
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

}
